package w3_c2_stack;

import java.util.Stack;

/**
 * Leetcode 括号匹配的问题。
 */
public class ValidParentheses {
    public static void main(String[] args) {
        String parentheses = "(){{}}}";
        Solution solution = new Solution();
        System.out.println(solution.isValid(parentheses));
        }
}


class Solution{
    /**
     * 判断s的括号是否closed。方法是：
     * 从头到位扫描括号串，若为左括号，则入栈；
     * 若为右括号，则判断其与栈顶括号是否匹配。若栈空或不匹配则匹配失败。
     * 若为其他字符，匹配失败。
     * 若扫描完括号串，且栈空，则匹配成功；否则失败。
     * @param s
     * @return
     */
    public boolean isValid(String s) {
//        Stack<Character> stack = new Stack<>();
        ArrayStack<Character> stack = new ArrayStack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(c == '{' || c == '[' || c == '(')//左括号
                stack.push(c);
            else if(c == '}' || c == ']' || c ==')'){//右括号
                if (stack.isEmpty())
                    return false;
                char top = stack.pop();
                if((top == '{' && c != '}') || (top =='[' && c != ']') || (top =='(' && c !=')'))
                    return false;
            }
            else //非括号
                return false;
        }
        return stack.isEmpty();
    }
}
